\subsection{Definition}
A register machine uses an alphabet \( \Sigma \), has finitely many states, and finitely many \emph{registers}, which are last-in first-out storage units containing a word \( w \in \mathbb W \).
The machine is able to access the last letter of the word, remove it, or push a new letter.
A \emph{configuration} or \emph{snapshot} of length \( n+1 \) is a tuple of the form \( (q, w_0, \dots, w_n) \in Q \times \mathbb W^{n+1} \).
A configuration defines the state of the computation at a particular point in time.

The transition function should now be of the form \( \delta \colon Q \times \mathbb W^{n+1} \to Q \times \mathbb W^{n+1} \).
However, not every such function represents a real computation; there are uncountably many such functions, and the action on the registers is unrestricted.
\begin{definition}
	Let \( \Sigma \) be an alphabet, and \( Q \) be a nonempty finite set of states.
	A tuple of the form
	\begin{align*}
		(0,k,a,q) &\in \mathbb N \times \mathbb N \times \Sigma \times Q \\
		(1,k,a,q,q') &\in \mathbb N \times \mathbb N \times \Sigma \times Q \times Q \\
		(2,k,q,q') &\in \mathbb N \times \mathbb N \times Q \times Q \\
		(3,k,q,q') &\in \mathbb N \times \mathbb N \times Q \times Q \\
	\end{align*}
	is called a \emph{\( (\Sigma, Q) \)-instruction}.
	For improved readability, we write
	\begin{align*}
		+(k,a,q) &= (0,k,a,q) \\
		?(k,a,q,q') &= (1,k,a,q,q') \\
		?(k,\varepsilon,q,q') &= (2,k,q,q') \\
		-(k,q,q') &= (3,k,q,q')
	\end{align*}
\end{definition}
Intuitively,
\begin{itemize}
	\item \( +(k,a,q) \) represents pushing the letter \( a \) onto register \( k \), then advancing to state \( q \).
	\item \( ?(k,a,q,q') \) checks if the letter \( a \) is currently at the top of register \( k \).
		If so, we advance to state \( q \), and otherwise, we advance to state \( q' \).
	\item \( ?(k,\varepsilon,q,q') \) checks if register \( k \) is empty.
		If so, we advance to state \( q \), and otherwise, we advance to state \( q' \).
	\item \( -(k,q,q') \) pops the topmost letter from register \( k \).
		If the register was already empty, we advance to state \( q \), and otherwise, we advance to state \( q' \).
\end{itemize}
These semantics are defined formally later.
Let \( \Instr(\Sigma, Q) \) be the set of \( (\Sigma,Q) \)-instructions.
This is in principle an infinite set, but finite if \( k \) is bounded.
\begin{definition}
	A tuple \( M = (\Sigma, Q, P) \) is called a \emph{\( \Sigma \)-register machine} if \( \Sigma \) is an alphabet, \( Q \) is a finite set of \emph{states} with two distinguished states \( q_S \neq q_H \), called the \emph{start state} and \emph{halt state} respectively, and \( P \colon Q \to \Instr(\Sigma,Q) \) is the \emph{program}.
	If \( Q = \qty{q_0, \dots, q_n} \), we can describe \( P \) as a finite collection of \emph{program lines} \( q_i \mapsto P(q_i) \).
	Since \( Q \) is finite, only finitely many registers \( k \) are referenced by \( P \); we call the largest such \( k \) the \emph{upper register index} of \( M \).
\end{definition}
\begin{definition}
	Let \( M \) be a register machine with upper register index \( n \) and \( \vb w = (w_0, \dots, w_n) \in \mathbb W^{n+1} \).
	For configurations \( C, C' \), we say \( M \) \emph{transforms} \( C \) into \( C' \) if one of the following holds.
	\begin{itemize}
		\item \( P(q) = +(k,a,q') \) and \( C' = (q', w_0, \dots, w_{k-1}, w_k a, w_{k+1}, \dots, w_m) \).
		\item \( P(q) =\, ?(k,a,q',q'') \), and
		\begin{itemize}
			\item \( w_k = wa \) for some \( w \) and \( C' = (q',w_0, \dots, w_m) \), or
			\item \( w_k \neq wa \) for all \( w \) and \( C' = (q'', w_0, \dots, w_m) \).
		\end{itemize}
		\item \( P(q) =\, ?(k,\varepsilon,q',q'') \), and
		\begin{itemize}
			\item \( w_k = \varepsilon \) and \( C' = (q',w_0, \dots, w_m) \), or
			\item \( w_k \neq \varepsilon \) and \( C' = (q'', w_0, \dots, w_m) \).
		\end{itemize}
		\item \( P(q) = -(k,q',q'') \), and
		\begin{itemize}
			\item \( w_k = \varepsilon \) and \( C' = (q',w_0, \dots, w_m) \), or
			\item \( w_k = wa \) and \( C' = (q'', w_0, \dots, w_{k-1}, w, w_{k+1}, \dots, w_m) \).
		\end{itemize}
	\end{itemize}
	Then we define the \emph{computation sequence} of \( M \) with input \( \vb w \) by \( C(0,M,\vb w) = (q_S,\vb w), C(k+1,M,\vb w) = C' \) where \( M \) transforms \( C(k,M,\vb w) \) into \( C' \).
\end{definition}
\begin{remark}
	This recursive definition requires that the length of \( \vb w \) is at least \( n + 1 \), where \( n \) is the upper register index.
	By convention, if \( \vb w \) is too short, we pad it with copies of the empty word \( \varepsilon \).
\end{remark}
\begin{remark}
	As defined above, all computation sequences are infinite, because every configuration is transformed by \( M \) into some other.
\end{remark}
\begin{definition}
	We say that the computation of \( M \) with input \( \vb w \) \emph{halts at time \( k \)} or \emph{in \( k \) steps} if \( k \) is the smallest natural such that \( C(k,M,\vb w) = (q_H,\vb v) \).
	In this case, we say that \( \vb v \) is the \emph{register content at time of halting}, or the \emph{output} of the computation.
	If such a \( k \) does not exist, we say the computation \emph{does not halt}.
\end{definition}

\subsection{Strong equivalence}
\begin{definition}
	We say that register machines \( M, M' \) are \emph{strongly equivalent} if for all \( k \) and \( \vb w \), \( C(k,M,\vb w) \) and \( C(k,M',\vb w) \) have the same register content, and for all \( \vb w \), we have that \( M \) halts after \( k \) steps with input \( \vb w \) if and only if \( M' \) halts after \( k \) steps with input \( \vb w \).
\end{definition}
\begin{remark}
	If \( \abs{Q} = \abs{Q'} \), then for every \( (\Sigma, Q, P) \) there exists a strongly equivalent register machine \( (\Sigma, Q', P') \) by relabelling the states in \( P \).
\end{remark}
\begin{proposition}[the padding lemma]
	Let \( M \) be a register machine.
	Then there are infinitely many different register machines that are strongly equivalent to \( M \).
\end{proposition}
\begin{proof}
	Let \( M = (\Sigma, Q, P) \).
	The register machine completely determines the computation sequence, so after adding a new state \( \hat q \) to \( Q \), \( \hat q \) is never a state in any computation sequence.
	So \( (\Sigma, Q \cup \qty{\hat q}, P \cup \qty{\hat p}) \) is strongly equivalent to \( M \) for any program line \( \hat p \) for \( \hat q \).
\end{proof}
\begin{proposition}
	Up to strong equivalence, there are only countably many register machines.
\end{proposition}
\begin{proof}
	Only the cardinality of \( Q \) matters up to strong equivalence.
	Let \( M_{n,k} \) be the collection of register machines with a fixed state set with \( \abs{Q} = n \) and upper register index at most \( k \).
	By checking cases, we find \( \abs{\Instr(\Sigma,Q)} = (k+1)n\abs{\Sigma} + (k+1)n^2\abs{\Sigma} + (k+1)n^2 + (k+1)n^2 = N_{n,k} \), which is finite.
	Therefore, there are \( N_{n,k}^n \) different programs, and hence \( \abs{M_{n,k}} = N_{n,k}^n \) is finite.
	Then the collection of all register machines up to strong equivalence is \( \bigcup_{n,k} M_{n,k} \) which is countable.
\end{proof}

\subsection{Performing operations and answering questions}
\begin{definition}
	An \emph{operation} is a partial function \( f \colon \mathbb W^{n+1} \rightharpoonup \mathbb W^{n+1} \).
	We write \( f(\vb w) \downarrow \) if \( \vb w \) lies in the domain of \( f \), and we say the operation \emph{is defined} or \emph{converges}.
	We write \( f(\vb w) \uparrow \) otherwise, and say that the operation is \emph{undefined} or \emph{diverges}.
	A register machine \( M \) \emph{performs} an operation \( f \) if for all \( \vb w \), \( f(\vb w) \downarrow \) if and only if \( M \) halts on input \( \vb w \), and in this case, the register content at time of halting is \( f(\vb w) \).
\end{definition}
\begin{example}
	The operation `never halt' is the empty function, \( \dom f = \varnothing \).
	Then any program that never references the halt state in the right hand side of a program line performs this operation.
	For example, \( q_S \mapsto +(0,a,q_S) \) and \( q_H \mapsto +(0,a,q_S) \) suffices.
\end{example}
\begin{remark}
	There are many register machines that perform the same operation, including many that are not strongly equivalent.
\end{remark}
\begin{example}
	The operation `halt without doing anything' is the function \( f(\vb w) = \vb w \) with \( \dom f = \mathbb W^{n+1} \).
	An example of a program to perform this is \( q_S \mapsto\, ?(0,a,q_H,q_H) \).
	This halts after one step, and preserves the register content.
\end{example}
\begin{definition}
	A \emph{question with \( k+1 \) answers} is a partition of \( \mathbb W^{n+1} \) into \( k + 1 \) sets \( A_i \).
	A register machine \emph{answers a question} if it has \( k + 1 \) \emph{answer states} \( \overline q_i \), and upon input of \( \vb w \), after finitely many steps its configuration is \( (\overline q_i, \vb w) \) for the value of \( i \) where \( \vb w \in A_i \).
\end{definition}
\begin{example}
	The question `is register \( i \) empty' is performed by \( q_S \mapsto\, ?(i, \varepsilon, \overline q_Y, \overline q_N) \).
	The question `is the final letter in register \( i \) the letter \( a \)' is performed by \( q_S \mapsto\, ?(i, a, \overline q_Y, \overline q_N) \).
\end{example}
The following lemma allows us to concatenate register machines, or alternatively, to perform subroutines.
\begin{lemma}[concatenation]
	Let \( M \) perform \( F \colon \mathbb W^{n+1} \rightharpoonup \mathbb W^{n+1} \), and \( M' \) perform \( F' \colon \mathbb W^{n+1} \rightharpoonup \mathbb W^{n+1} \).
	Then we can construct a register machine \( \hat M \) which performs \( F' \circ F \).
\end{lemma}
\begin{remark}
	If \( F(\vb w) \uparrow \), then \( (F' \circ F)(\vb w) \uparrow \).
	If \( F(\vb w) \downarrow \) and \( F'(F(\vb w)) \uparrow \), then \( (F' \circ F)(\vb w) \uparrow \).
	Otherwise, \( (F' \circ F)(\vb w) \downarrow \).
\end{remark}
\begin{proof}
	We may assume without loss of generality that the state sets of the two machines are disjoint.
	We define \( \hat Q = Q \cup Q' \setminus \qty{q_H} \).
	We write \( P^\star \) for the program \( P \) with the rule \( q_H \mapsto P(q_H) \) removed, and then all instances of \( q_H \) replaced with \( q_S' \).
	We then define \( \hat P = P^\star \cup P' \).
	Then \( \hat M = (\Sigma, \hat Q, \hat P) \) clearly performs \( F' \circ F \).
\end{proof}
\begin{lemma}[case distinction]
	Let \( \symsfup Q \) be a question with \( k + 1 \) answers.
	Let \( F_i \colon \mathbb W^{n+1} \rightharpoonup \mathbb W^{n+1} \) be operations for \( i \leq k \).
	Let \( M \) be a register machine that answers \( \symsfup Q \), and let \( M_i \) be register machines that perform \( F_i \).
	Then there is a register machine that performs the operation given by \( G(\vb w) = F_i(\vb w) \) if \( \vb w \in A_i \).
\end{lemma}
\begin{proof}
	We assume that \( Q \) is disjoint from each \( Q_i \), and \( \bigcap_{i \leq k} Q_i = \qty{q_H} \).
	Let \( P_i^\star \) be \( P_i \) where all occurrences of \( q_{S,i} \) are replaced with the \( i \)th answer state \( \overline q_i \).
	Define \( Q^\star = Q \cup \bigcup_{i \leq k} Q_i \setminus \qty{q_{S,i}} \) and \( P^\star = P \cup \bigcup_{i \leq k} P_i^\star \).
	Then \( M^\star = (\Sigma, Q^\star, P^\star) \) performs \( G \).
\end{proof}

\subsection{Register machine API}
We can perform many different operations and answer many different questions using register machines.
We say that a register is \emph{unused} if no program line references it.
A register is \emph{empty} if it contains the empty word.
Registers that are used only for computation and not the output are sometimes called \emph{scratch space} or \emph{scratch registers}.
\begin{itemize}
	\item Consider
	\[ F(\vb w) = \begin{cases}
		\vb w & w_i \neq \varepsilon \\
		\uparrow & w_i = \varepsilon
	\end{cases} \]
	The question `is register \( i \) empty' is performed by a register machine, and in this case, the `never halt' operation can be performed; in the other case, the `halt without doing anything' operation can be performed.
	\item The operation `delete the final letter of register \( i \) if it exists' is performed by the program \( q_S \mapsto -(i,q_H,q_H) \).
	\item The operation `add letter \( a \) to register \( i \)' is performed by \( q_S \mapsto +(i,a,q_H) \).
	Note that this machine also performs the operation `guarantee that the \( i \)th register is nonempty'.
	\item The operation `delete the content of register \( i \)' is performed by \( q_S \mapsto -(i,q_H,q_S) \).
	\item We can perform the operation `add a fixed word \( w \) to register \( i \)'.
	If \( w = a_0 \dots a_\ell \), we use the concatenation lemma to perform the operation `add letter \( a_j \) to register \( i \)' for each letter in the word.
	\item The operation `replace the register content of \( i \) with the word \( w \)' can be performed by concatenating the operations `delete the content of register \( i \)' and `add \( w \) to register \( i \)'.
	\item We can answer the question `what is the final letter of register \( i \)'.
	This question has \( \abs{\Sigma} + 1 \) answers, since the register could be empty.
	For each letter \( a_j \in \Sigma \), we ask the question `does register \( i \) end in letter \( a_j \)', and if yes, go to the corresponding answer state \( \overline q_j \), and if not, go to a state that asks the next question in the sequence.
	If no question answers `yes', the register is empty, and we go to an answer state \( \overline q_\varepsilon \).
	\item In particular, we can perform the operation `copy the final letter of register \( i \) into register \( j \) if it exists', by asking what this letter is, and then in each case, pushing the relevant letter onto register \( j \).
	\item We can also `move the final letter of register \( i \) into register \( j \) if it exists' by first copying the letter and then removing the original from register \( i \).
	\item The operation `move the content of register \( i \) into register \( j \) in reverse order' is accomplished by repeatedly moving a single letter until no more letters lie in register \( i \).
	\item The operation `move the content of register \( i \) into register \( j \) in the correct order' can be performed by considering an unused empty register \( k \).
	We move the register content from \( i \) to \( k \) in reverse order and then from \( k \) to \( j \) in reverse order.
	\item The operation `reverse the content of register \( i \)' is performed by moving it in reverse order to an unused empty register \( j \), and then moving this into \( i \) in the correct order.
	\item The operation `move the content of register \( i \) into registers \( j \) and \( k \) in reverse order' is easily performed by copying the final letter of register \( i \) into \( j \) and then into \( k \), then removing the final letter in register \( i \) iteratively until it is empty.
	\item The operation `copy the content of register \( i \) into register \( j \) in reverse order' is accomplished by moving the content of register \( i \) into \( j \) and an unused empty register \( k \), and then moving the register content of \( k \) into \( i \) in reverse order.
	\item The operation `copy the content of register \( i \) into register \( j \) in the correct order' is accomplished by copying in the reverse order, and then reversing the content of register \( j \).
	\item Consider the question `is the content of register \( i \) the word \( w \)'.
	Let \( w = a_0 \dots a_k \).
	We define the subroutine \( S_\ell \) to answer the question `is \( a_\ell \) the final letter of register \( i \)'.
	If no, move to a state \( q_N \).
	If yes, move the final letter to an unused empty register \( k \) and run subroutine \( S_{\ell-1} \), or if \( \ell = 0 \), move to a state \( q_Y \).
	At state \( q_N \) we move the content of \( k \) to \( i \) and answer \( \overline q_N \), and at state \( q_Y \) we move the content of \( k \) to \( i \) and answer \( \overline q_Y \).
\end{itemize}
